Definition

Suppose function ff which is convex and differentiable, where domf=ℝn\mathrm{dom} f = \mathbb{R}^n. then any maximizer x∗x^* of yTx−f(x)y^T x - f(x) satisfies y=∇f(x∗)y = \nabla f(x^*), conversely, if x∗x^* satisfies y=∇f(x∗)y = \nabla f(x^*), then x∗x^* maximizes yTx−f(x)y^T x - f(x). Therefore, if y=∇f(x∗)y = \nabla f(x^*), have

f∗(y)=x∗T∇f(x∗)−f(x∗)f^*(y) = x^{*T} \nabla f(x^*) - f(x^*)

Or, let z∈ℝnz \in \mathbb{R}^n be arbitary, define y=∇f(z)y = \nabla f (z), then

f∗(y)=zT∇f(z)−f(z)f^*(y) = z^T \nabla f(z) - f(z)

or simply, given function ff,

f∗(y)=supx∈dom⁡(f)⁡(yTx−f(x))f^*(y) = \sup_{x \in \operatorname{dom}(f)} (y^T x - f(x))

Notes

  • Intuition: for given slope, find "highest" line that minorizes (i.e. lives below) function, i.e. line with largest possible intercept, which is −f∗(y)-f^*(y)
  • role in Fenchel duality

References

  1. https://en.m.wikipedia.org/wiki/Convex_conjugate
  2. S. P. Boyd and L. Vandenberghe, Convex optimization, 2004, p. 95. [Online]. Available: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf doi: 10.1017/CBO9780511804441 ISBN: 9780521833783
  3. https://www.stat.cmu.edu/~siva/teaching/725/lec12.pdf